package Day2025_03_24;

public class LeetCode322 {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 0; i <= amount; i++) dp[0][i] = 0x3f3f3f3f;
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1] && dp[i][j - coins[i - 1]] != -1)
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        }
        return dp[n][amount] >= 0x3f3f3f3f ? -1 : dp[n][amount];
    }
}

